#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int cnt;
	cin >> cnt;
	while(cnt--){
		int n,t;
		cin >> n >> t;
		string s;
		cin >> s;
		vector<int> pos;
		pos.reserve(n);
		int rindex = 0;
		while(s[rindex] == '0'){
			++rindex;
		}
		pos.push_back(rindex);
		int lindex = n - 1;
		while(s[lindex] == '0'){
			lindex = (lindex - 1 + n) % n;
		}
		if(rindex != lindex){
			pos.push_back(lindex);
		}
		
		int maxl = 0;
		int fireindex;
		maxl = max(maxl,rindex + n - 1 - lindex);
		lindex < n - 1 ? fireindex = lindex + 1 : fireindex = -1; 
		
		++rindex;
		while(rindex < lindex){
			int len = 0;
			while(s[rindex] == '0'){
				++len;
				++rindex;
			}
			if(rindex != lindex){
				pos.push_back(rindex);
			}
			if(len > maxl){
				maxl = len;
				fireindex = rindex - 1;
			}
			++rindex;
		}
		
		if(fireindex == -1){
			cout << 0;
			if(cnt) cout << endl;
			continue;
		}
		
		for(auto fire : pos){
			int i = fire;
			bool lf = true,rf = true;
			s[fireindex] = '1';
			
			for(int j = 1; j <= t; ++j){
					int left = (i - j + n) % n;
					int right = (i + j) % n;
					if(lf){
						if(s[left] == '1'){
							lf = false;
						}
						if(lf){
							s[left] = '1';
						}
					}
					if(rf){
						if(s[right] == '1'){
							rf = false;
						}
						if(rf){
							s[right] = '1';
						}
					}
				}
		}
		
//		for(int i = 0; i < n; ++i){
//			cout << i << "===" << s[i] << endl;
//		}
		
		int ret = 0;
		
		for(int i = 0; i < n; ++i){
			if(s[i] == '0'){
				++ret;
			}
		}
		
		cout << ret;
		if(cnt) cout << endl;
	}
	
	return 0;
}

